package array;

/**
 * 阿里面试题：
 * <li>给定一个数组 a，包含 n 个整数</li>
 * <li>再给定一个整数 k，可以给数组中任意整数加 1，总共可以加 k 次</li>
 * <li>加完 k 次后，找到数组中的最大值。最后要求得一个最小的最大值</li>
 *
 * @author Ringo
 * @date 2021/8/31 21:40
 */
public class MaxValueAfterIncrement {

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5};
        System.out.println(solution(nums, 10));
    }


    /**
     * 所谓的一共加k次， 最后求最小的最大值， 意思是， 加k次1时， 应该尽量平铺， 使最大值不大于原来数组的最大值，就是一直往比较小的值上加。
     * 就像倒水，优先往低处流。
     * 所以思路就有了, 假设原数组最大值是p。
     * <br/>
     * <hr/>
     * 解题步骤：<br/>
     * <li>首先求原数组的每个值跟p的差， 然后把这些差值求和， 用sum表示， 这个sum， 就是加1时优先加的地方（次数）。</li>
     * <li>如果k比sum小， 表示坑填不满， 结果就是p。</li>
     * <li>如果k比sum大， 表示填平坑后， 还有剩余要加1， 这时就看剩余的1（k-sum）， 跟数组长度的关系， 看能平铺几层。 即求商和余数，记为x和y。</li>
     * <li>如果y==0，则可以铺x层，结果就是p+x; 如果y>0， 可以铺x+1层， 结果就是p+x+1。</li>
     */
    public static int solution(int[] nums, int k) {
        if (nums == null || nums.length == 0)
            return -1;
        int p = maxInArray(nums);

        int n = nums.length;

        // sum 保存最大值 p 和其他元素的差的和
        int sum = 0;
        for (int num : nums) {
            sum += p - num;
        }

        // 坑没有填平
        if (k < sum) return p;

        // 到这里表示 坑填平了

        int x = (k - sum) / n;      // 剩余的又平铺几层？
        int y = (k - sum) % n;      // 是正好平铺吗？

        // 正好平铺
        if (y == 0) return p + x;

        // 不是正好平铺
        return p + x + 1;
    }

    // 求数组最大值
    public static int maxInArray(int[] nums) {
        if (nums == null || nums.length == 0)
            throw new IllegalArgumentException("参数 nums 不能为空, 并且数组元素长度不能为0！");
        int max = nums[0];
        for (int num : nums) {
            max = Math.max(num, max);
        }
        return max;
    }
}
